#include<bits/stdc++.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int n,k;
int a[N];
struct Arrar{
	int a[N];
	inline friend Arrar operator*(Arrar a,Arrar b){
		For(i,1,n){
			a.a[i]=b.a[a.a[i]];
		}
		return a;
	}
}res,A;
inline int check(){
	For(i,1,n) res.a[i]=a[i],A.a[i]=a[i];
	int b=k-1;
	while(b){
		if(b&1) res=res*A;
		b>>=1;
		if(!b) break;
		A=A*A;
	}
	int flag=0;
	For(i,1,n) flag+=(res.a[i]!=1);
	return flag;
}
inline Arrar work(){
	For(i,1,n) res.a[i]=a[i],A.a[i]=a[i];
	int b=k-1;
	while(b){
		if(b&1) res=res*A;
		if(b==1) break;
		b>>=1;
		if(!b) break;
		A=A*A;
	}
	return res;
}
int in[N];
vector<int>q[N];
int dep[N],mx[N],p[N];
int f[N];
int gg[N];
int mp[N],ss[N];
multiset<int>s;
bool vis[N];
int answer=1e16;
int lst[N];
void dfs(int x){
	if(x==n+1){
		int p=0;
		For(i,1,n) if(lst[i]!=a[i]) p++;
		if(answer<=p) return;
//		For(i,1,n) cout<<a[i]<<" ";
//		puts("");
//		cout<<check()<<endl;
		if(check()) return;
		answer=min(answer,p);
		return;
	}
	For(i,1,n){
		a[x]=i;
		dfs(x+1);
		a[x]=0;
	}
}
signed main(){
	freopen("lost.in","r",stdin);
	freopen("lost.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	n=read(),k=read();
	int ans=0;
	For(i,1,n) lst[i]=a[i]=read();
	if(!check()){
		puts("0");
		return 0;
	}
	if(n<=8){
		dfs(1);
		cout<<answer<<endl;
		return 0;
	}
	if(k==1){
		For(i,1,n)ans+=(a[i]!=1);
		printf("%lld\n",ans);
		return 0; 
	}
	For(i,1,1) {
		if(a[i]>i){
			a[i]=1;
			ans++;
		}
	}
	For(i,2,n) in[a[i]]++,q[i].push_back(a[i]);
	memset(mx,-0x3f,sizeof(mx));
	queue<int>Q;
	For(i,1,n){
		if(!in[i]) Q.push(i),mx[i]=1;
	}
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(auto v:q[u]){
			in[v]--;
			if(mx[v]<mx[u]%(k-1)+1){
				p[v]=u;
				mx[v]=max(mx[v],mx[u]%(k-1)+1);
			}
			dep[v]=max(dep[u]+1,dep[v]) ;
			if(!in[v]){
				Q.push(v);
			}
		}
	}
	For(i,1,n ) q[i].clear();
	For(i,2,n) in[i]++,q[a[i]].push_back(i);
	For(i,1,n){
		if(!in[i]) Q.push(i);
	}
	vis[1]=1;
//	For(i,1,n) cout<<mx[i]<<' ';
//	puts("");
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(auto v:q[u]){
			in[v]--;
			mx[v]=max(mx[v],(mx[u]-1+k-1)%(k-1));
			if(!in[v]){
				Q.push(v);
			}
		}
	}
	int res=1e16;
	For(i,1,n){
		mp[mx[i]%(k-1)]++;
	}
	For(i,0,k-2) res=min(res,mp[i]);
//	if(!check()){puts("-1");}
	printf("%lld\n",ans+res);
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}
/*
6 4
1 1 2 3 4 5
*/
